package interviewClassic150;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Merge {
    public int[][] merge(int[][] intervals) {
        //先将数组排序
        Arrays.sort(intervals,(x1,x2)->{
            //首先按照第一个元素排序
            if (x1[0] != x2[0]) return x1[0] - x2[0];
            //在第一个元素相等时,按照第二个元素排序
            return x1[1] - x2[1];
        });
        //当前区间
        int[] curRange = intervals[0];
        int n = intervals.length;
        List<int[]> res = new ArrayList<>();
        for (int i = 1; i < n; i++) {
            //当前遍历到的区间与现有区间是否有重叠
            if (intervals[i][0] <= curRange[1]) {
                //合并区间
                curRange[1] = Math.max(curRange[1],intervals[i][1]);
            } else {
                //无重叠
                //将现有区间加入结果集
                res.add(curRange);
                //重置现有区间
                curRange = intervals[i];
            }
        }
        //最后一个区间，加入结果集
        res.add(curRange);
        //转换成数组
        return res.toArray(new int[0][]);
    }

    @Test
    public void test() {
        int[][] intervals = {{1,3},{2,6},{8,10},{15,18}};
        int[][] merge = merge(intervals);
        System.out.println(merge);
    }
}
